/*
题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。

题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
可将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。

解答如下：
先解决第1题

定义1：若所有火柴数异或为0，则该状态被称为利他态，用字母T表示；否则，为利
己态，用S表示。

定理1：对任何S态，存在方法，从其中取一堆中的若干根，使状态变为T态。

引理1.1 ：A(i)为非副整数，i=1..n, 记c=A(1) xor A(2) xor …… xor A(n),
若c>0,则存在A(t), A(t) xor c <A(t)

证明： 把c表示成二进制，记它的二进制数的最高位为第p位，
则必然存在一个A(t),它二进制的第p位也是1。（否则，若所有的A(i)的第p位都是0，
c的第p位就也为0，矛盾！）
x=a(t) xor c 的第p位将为1 xor 1,即0；
又因为c的最高位为p，所以x高于p位的值不变。所以必有x<a(t).即a(t) xor c<a(t).
命题得证。

再来证定理1.
证明：
设共有n堆火柴，每堆的数目分别为A(i)，i=1..n，A(i)为非副整数.
记c=A(1) xor A(2) xor …… xor A(n),
因为是S态，所以 c>0;
所以存在A(t), A(t) xor c <A(t)。
A(t)' = A(t) xor c <A(t)
c' = A(1) xor A(2) xor … xor A(t)' xor … xor A(n)
= A(1) xor A(2) xor … xor A(t) xor c xor … xor A(n)
= A(1) xor A(2) xor … xor A(t) xor … xor A(n) xor c
= c xor c = 0
所以，用把第t堆由A(t)根取成A(t)' 根（A(t)' = A(t) xor c <A(t) )，状态成为T态。
故命题成立。 #

定理2：T态，取任何一堆的若干根，都将成为S态。

证明：反证法：
反设存在一堆，记为第m堆，从中取了若干根，根数由A(m)变为A(m)' .
A(m)>A(m)' 状态均为T态。
记c=A(1) xor A(2) xor … xor A(m) xor… xor A(n),
记c'=A(1) xor A(2) xor … xor A(m)' xor… xor A(n),
c=0;c'=0;
所以有 0= A(1) xor A(2) xor … xor A(m) xor… xor A(n)
= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n) xor A(m)
= d xor A(m)
d= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n)
故 A(m)=d
同理， d xor A(m)' =0
A(m)'= d
所以，A(m)'=A(m) . 矛盾！
故反设不成立。原命题成立。 #

定理 3：S态，只要方法正确，必赢。

最终胜利即由S态转变为T态，任何一个S态，只要把它变为T态，（由定理一，可以把它
变成T态。）对方只能把T态转变为S态(定理2)。这样，所有S态向T态的转变都可以有己
方控制，对方只能被动地实现由T态转变为S态。故S态必赢。 #

定理4：T态，只要对方法正确，必败。

由定理3易得。

我们再来处理第2题。我们会发现两题会有一些相同之处，控制S->T态的人控制着主动权
。经过分析，我们有以下结论：

定义2：若一堆中仅有1根火柴，则被称为孤单堆。若大于1根，则称为充裕堆。

定义3：T态中，若充裕堆的堆数大于等于2，则称为完全利他态，用T2表示；若充裕堆的
堆数等于0，则称为部分利他态，用T0表示。

定理4：不存在充裕堆数为1的T态。

证明：
孤单堆的根数异或只会影响二进制的最后一位，但充裕堆会影响高位（非最后一位）。
一个充裕堆，高位必有一位不为0，则所有根数异或不为0。故不会是T态。

定义4：S态中，若充裕堆的堆数大于等于2，则称为完全利己态，用S2表示；若充裕堆的
堆数等于1，则称为自主利己态，用S1表示; 若充裕堆的堆数等于0，则称为部分利己态
，用S0表示。

定理4：S0态，即仅有奇数个孤单堆，必败。T0态必胜。

证明：S0态，其实就是每次只能取一根。每次第奇数根都由己取，第偶数根都由对方取
，所以最后一根必己取。败。
同理, T0态必胜#

定理5：S1态，只要方法正确，必胜。

证明：若此时孤单堆堆数为奇数，把充裕堆取完；否则，取成一根。
这样，就变成奇数个孤单堆，由对方取。
由定理4，对方必输。己必胜。 #

定理6：S2态不可转一次变为T0态。

证明：充裕堆数不可能一次由2变为0。得证。 #

定理7：S2态可一次转变为T2态。

证明：由定理1，S态可转变为T态，态可一次转变为T态
又由定理6，S2态不可转一次变为T0态，
所以转变的T态为T2态。 #

定理8：T2态，只能转变为S2态或S1态。

证明：. 由定理2，T态必然变为S态。
由于充裕堆数不可能一次由2变为0，所以此时的S态不可能为S0态。
命题得证。

定理9：S2态，只要方法正确，必胜.

证明：方法如下：
1） S2态，就把它变为T2态。（由定理7）
2） 对方只能T2转变成S2态或S1态(定理8)
若转变为S2, 转向1）
若转变为S1, 这己必胜。（定理5）

定理10：T2态必输。

证明：同9。

综上所述，必输态有： T2,S0
必胜态： S2,S1,T0.

两题比较：

第一题的全过程其实如下：
S2->T2->S2->T2-> …… ->T2->S1->T0->S0->T0->……->S0->T0(全0)
第二题的全过程其实如下：
S2->T2->S2->T2-> …… ->T2->S1->S0->T0->S0->……->S0->T0(全0)
下划线表示胜利一方的取法。
是否发现了他们的惊人相似之处。
我们不难发现(见加黑部分)，S1态可以转变为S0态（第二题做法），也可以转变为T0（
第一题做法）。哪一方控制了S1态，他即可以有办法使自己得到最后一根（转变为T0）
,也可以使对方得到最后一根（转变为S0）。
所以，抢夺S1是制胜的关键！
为此，始终把T2态让给对方，将使对方处于被动状态，他早晚将把状态变为S1.(见定理
9的证明).
*/

import java.io.*;

public class Main {
    static int ch;

    public static int nextInt() {
        int ret = 0;
        try {
            do {
                ch = System.in.read();
            } while (Character.isWhitespace(ch));
            while (Character.isDigit(ch)) {
                ret *= 10;
                ret += Character.digit(ch, 10);
                ch = System.in.read();
            }
        } catch (IOException e) {
        }
        return ret;
    }

    public static void main(String[] args) {
        int re = nextInt();
        for (int ri = 1; ri <= re; ++ri) {
            int n = nextInt();
            int c = 0, s = 0;
            for (int i = 0; i < n; ++i) {
                int a = nextInt();
                if (a > 1) {
                    ++c;
                }
                s ^= a;
            }
            if ((s == 0 && c > 0) || (c == 0 && s > 0)) {
                System.out.println("2");
            } else {
                System.out.println("1");
            }
        }
    }
}

//Run ID    Submit Time     Judge Status    Problem ID      Language    Run Time(ms)    Run Memory(KB)      User Name
//1801479   2009-03-24 08:34:58     Accepted    2507    Java    0   60  watashi@Zodiac

// 2012-09-07 01:25:37 | Accepted | 2507 | Java | 60 | 211 | watashi | Source
